#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = 110;
const int M = 2510;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int n,m,k,u[M],v[M],w[M];

struct matrix{
	ll arr[N][N];int x;
	matrix(int _x = 0):x(_x){memset(arr,0x3f,sizeof(arr)); for(int i = 0;i < x;i++) arr[i][i] = 0;}
	const ll * operator [](int x)const{return arr[x];}
	ll * operator [](int x){return arr[x];}
	friend matrix operator * (matrix a,matrix b){
		matrix c(a.x);
		for(int i = 0;i < a.x;i++)
			for(int j = 0;j < a.x;j++)
				for(int k = 0;k < a.x;k++)
					c[i][k] = min(a[i][j] + b[j][k],c[i][k]);
		return c;
	}
}a,b;
	
int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,m = in,k = in;
	a = matrix(n);
	for(int i = 0;i < m;i++){
		u[i] = in - 1,v[i] = in - 1,w[i] = in;
		a[u[i]][v[i]] = w[i];
	}
	for(int k = 0;k < n;k++)
		for(int i = 0;i < n;i++)
			for(int j = 0;j < n;j++)
				a[i][j] = min(a[i][k] + a[k][j] , a[i][j]);
	b = a;
	for(int i = 0;i < m;i++)
		for(int x = 0;x < n;x++)
			for(int y = 0;y < n;y++)
				b[x][y] = min(b[x][y],a[x][u[i]] + a[v[i]][y] - w[i]);
	if(k) for(;k;k >>= 1,b = b * b) if(k & 1) a = a * b;
	printf("%lld\n",a[0][n-1]);
	return 0;
}

